4.13模拟赛 T3 高维部分和

发表于 | 更新于 | 评论数： | 阅读次数：

题面：http://www.51nod.com/Challenge/Problem.html#!#problemId=2383

输入一个长度为n的数组a[i]，下标从0开始（0到n-1）
保证n是2的整数次幂，
对于每个i (0 <= i < n)
求所有满足((i & j) == j)的a[j]之和。

其中&表示按位与，即C++和C中的&，Pascal中的and。
对于100%的数据，1 <= n <= 220, 0 <= a[i] <= 1000
对于70%的数据，1 <= n <= 215,
对于50%的数据，1 <= n <= 210,

考试的时候居然忽略了提示QWQ！！！

虽然这是一个简单题，但是为了降低难度，你可以看看下面的解释。
对于一个一维数组求部分和，可以使用如下代码

1
for (int i = 1; i <= n; i++)a[i] += a[i - 1];

对于一个二维数组求部分和，可以使用如下代码

1
2
3
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];

或如下代码

1
2
3
4
5
6
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        a[i][j] += a[i][j - 1]
for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++) 
        a[i][j] += a[i - 1][j]

第二份代码看起来更麻烦更慢，来考虑一下三维的情况。

1
2
3
4
5
6
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++)
            a[i][j][k] += a[i][j][k - 1] + a[i][j - 1][k] + a[i - 1][j][k];
            a[i][j][k] -= a[i][j - 1][k - 1] + a[i - 1][j - 1][k] + a[i - 1][j][k - 1];
            a[i][j][k] += a[i - 1][j - 1][k - 1];

或如下代码

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++)
            a[i][j][k] += a[i][j][k - 1];
for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++) 
        for (int k = 1; k <= n; k++) 
            a[i][j][k] += a[i][j - 1][k];
for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= n; j++) 
        for (int k = 1; k <= n; k++)
            a[i][j][k] += a[i - 1][j][k];

第二份代码就不一定更慢了（第二份复杂度大约3n^3，第一份复杂度大概8n^3）
随着维度更高，第一份代码容斥时项数越来越多，而第二份只是多一次遍历整个数组，优势越来越大。
同样的思路能不能推广到更高维的情况呢？

输入

1
2
第一行一个整数n
接下来n行n个整数，表示a[i]

输出

1
输出共n行，其中第i(0 <= i < n)行表示i的答案。

输入样例

1
2
3
4
5
6
7
8
9
8
1
2
4
8
16
32
64
128

输出样例

1
2
3
4
5
6
7
8
1
3
5
15
17
51
85
255

首先，这题一眼容斥，又或者是FWT/FMT？（没差，都不会）

还记得有两个**学了一上午FMT/FMT觉得自己会了的心酸历程

但是一看题目说是简单题？！

让我们来看看提示（！一定要看啊）

写的是 容斥 与 从低位到高位一维一维做前缀和 这两种方法的区别

！！一维一维做前缀和？？？！！！

当二维时举个例子

显然由题意可得当 (i&j==j) 时 j是i的子集

所以：

$f[0]=a[0]$

$f[1]=a[1]+a[0]$

$f[2]=a[2]+a[0]$

$f[3]=a[3]+a[2]+a[1]+a[0]$

然后我们让他更显然：

$f[0][0]=a[0]$

$f[0][1]=a[1]+a[0]$

$f[1][0]=a[2]+a[0]$

$f[1][1]=a[3]+a[2]+a[1]+a[0]$

然后根据提示：先转移最后一维

  • $f$初值为输入值

$f[0][1]+=f[0][0]$

$f[1][1]+=f[1][0]$

第二维：

$f[1][0]+=f[0][0]$

$f[1][1]+=f[0][1]$

而这道题就是一个21维的$f$数组，如果有铁头娃想要21重循环，写21次的话，也不是不行

当然我选择状压（害怕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int n,f[1<<22];
int read()
{
    int x=0; char s=getchar();
    while(!isdigit(s))s=getchar();
    while(isdigit(s))
    {
        x=(x<<3)+(x<<1)+(s^48);
        s=getchar();
	}
    return x;
}
void write(int x)
{
    int y=10,len=1;
    while(y<=x)y*=10,len++;
    while(len--)y/=10,putchar(x/y+48),x%=y;
}
int main()
{
    n=read();
    for(int i=0;i<n;i++)f[i]=read();
    int g=log2(n);
    for(int i=0;i<=g;i++)
        for(int j=0;j<n;j++)
            if((1<<i)&j)f[j]+=f[(1<<i)^j];//这一维的状态为1的话就可以加上这一维状态为0的f值
    for(int i=0;i<n;i++)write(f[i]),puts("");
}

总的来说，这题还是很遗憾，没有看提示（看了提示也不一定能写出来啊喂）

注意io优化，看清题目！